home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cocktail / docme.lha / doc.me / lalr.me < prev    next >
Text File  |  1992-09-25  |  75KB  |  2,292 lines
  1. .\" use: pic | tbl | eqn | ditroff -me
  2. .\"
  3. .\"    "@(#)bibmac.me    2.2    9/9/83";
  4. .de IP
  5. .ip \\$1 \\$2
  6. ..
  7. .de LP
  8. .lp
  9. ..
  10. .\"    @(#)bmac.std    2.2    9/9/83;
  11. .\" standard format troff commands
  12. .\" citation formatting strings
  13. .ds [[ [
  14. .ds ]] ]
  15. .ds ], ,\|
  16. .ds ]- -
  17. .ds [. " \&
  18. .ds .] .
  19. .ds [, " \&
  20. .ds ,] ,
  21. .ds [? " \&
  22. .ds ?] ?
  23. .ds [: " \&
  24. .ds :] :
  25. .ds [; " \&
  26. .ds ;] ;
  27. .ds [! " \&
  28. .ds !] !
  29. .ds [" " \&
  30. .ds "] \&"
  31. .ds [' " \&
  32. .ds '] '
  33. .ds [< " \&
  34. .ds >]
  35. .\" reference formmating strings
  36. .ds a] " \&
  37. .ds b] , \&
  38. .ds c] , \&
  39. .ds n] "\& and \&
  40. .ds m] "\& and \&
  41. .ds p] .
  42. .\" reference formmating macros
  43. .de s[   \" start reference
  44. .nh
  45. .IP [\\*([F] 5m
  46. ..
  47. .de e[   \" end reference
  48. .[-
  49. ..
  50. .de []   \" start to display collected references
  51. .LP
  52. ..
  53. .de ][   \" choose format
  54. .ie !"\\*([J"" \{\
  55. .    ie !"\\*([V"" .nr t[ 1    \" journal
  56. .    el            .nr t[ 5    \" conference paper
  57. .\}
  58. .el .ie !"\\*([B"" .nr t[ 3    \" article in book
  59. .el .ie !"\\*([R"" .nr t[ 4    \" technical report
  60. .el .ie !"\\*([I"" .nr t[ 2    \" book
  61. .el                .nr t[ 0    \" other
  62. .\\n(t[[
  63. ..
  64. .de 0[   \" other
  65. .s[
  66. .if !"\\*([A"" \\*([A\\c
  67. .if !"\\*([T"" , \\*([T\\c
  68. .if !"\\*([V"" , Vol. \\*([V\\c
  69. .if !"\\*([O"" , \\*([O\\c
  70. .if !"\\*([D"" , \\*([D\\c
  71. \&.
  72. .e[
  73. ..
  74. .de 1[ \" journal article
  75. .s[
  76. .if !"\\*([A"" \\*([A,
  77. .if !"\\*([T""  \\*([T,
  78. \\fI\\*([J \\*([V\\fP\c
  79. .if !"\\*([N"" ,\\*([N
  80. .if !"\\*([D"" (\\*([D)\c
  81. .if !"\\*([P"" , \\*([P\c
  82. .if !"\\*([I"" , \\*([I\c
  83. \\&.
  84. .if !"\\*([O"" \\*([O.
  85. .e[
  86. ..
  87. .de 2[ \" book
  88. .s[
  89. .ie !"\\*([A"" \\*([A,
  90. .el .if !"\\*([E"" \{\
  91. .       ie \\n([E-1 \\*([E, eds.,
  92. .       el \\*([E, ed.,\}
  93. .if !"\\*([T"" \\fI\\*([T\\fP,
  94. .rm a[
  95. .if !"\\*([I"" .ds a[ \\*([I
  96. .if !"\\*([C"" \{\
  97. .       if !"\\*(a["" .as a[ , \\&
  98. .       as a[ \\*([C\}
  99. .if !"\\*([D"" \{\
  100. .       if !"\\*(a["" .as a[ , \\&
  101. .       as a[ \\*([D\}
  102. \\*(a[.
  103. .if !"\\*([G"" Gov. ordering no. \\*([G.
  104. .if !"\\*([O"" \\*([O.
  105. .e[
  106. ..
  107. .de 3[ \" article in book
  108. .s[
  109. .if !"\\*([A"" \\*([A,
  110. .if !"\\*([T"" \\*([T,
  111. in \\fI\\*([B\\fP\c
  112. .if !"\\*([V"" , vol. \\*([V
  113. .if !~\\*([E~~ \{\
  114. .       ie , \\n([E-1  \\*([E (editors)\c
  115. .       el , \\*([E (editor)\c\}
  116. .if !"\\*([I"" , \\*([I\c
  117. .if !"\\*([C"" , \\*([C\c
  118. .if !"\\*([D"" , \\*([D\c
  119. .if !"\\*([P"" , \\*([P\c
  120. \\&.
  121. .if !"\\*([O"" \\*([O.
  122. .e[
  123. ..
  124. .de 4[ \" report
  125. .s[
  126. .if !"\\*([A"" \\*([A,
  127. .if !~\\*([E~~ \{\
  128. .       ie \\n([E-1 \\*([E, editors.
  129. .       el \\*([E, editor.\}
  130. \\*([T,
  131. \\*([R\c
  132. .if !"\\*([G"" \& (\\*([G)\c
  133. .if !"\\*([I"" , \\*([I\c
  134. .if !"\\*([C"" , \\*([C\c
  135. .if !"\\*([D"" , \\*([D\c
  136. \\&.
  137. .if !"\\*([O"" \\*([O.
  138. .e[
  139. ..
  140. .de 5[ \" conference paper
  141. .s[
  142. .if !"\\*([A"" \\*([A,
  143. .if !"\\*([T"" \\*([T,
  144. \\fI\\*([J\\fP,
  145. .if !"\\*([C"" \\*([C,
  146. .if !"\\*([D"" \\*([D\c
  147. .if !"\\*([P"" , \\*([P\c
  148. \\&.
  149. .if !"\\*([O"" \\*([O.
  150. .e[
  151. ..
  152. .de [-   \" clean up after yourself
  153. .rm [A [B [C [D
  154. .rm [E [F [G
  155. .rm [I [J [K
  156. .rm [N [O [P
  157. .rm [R [T
  158. .rm [V [W
  159. ..
  160. .\"    @(#)bmac.std    2.2    8/24/83;
  161. .\" standard format troff commands
  162. .\" citation formatting strings
  163. .ds [[ [
  164. .ds ]] ]
  165. .ds ], ,\|
  166. .ds ]- -
  167. .ds [. " \&
  168. .ds .] .
  169. .ds [, " \&
  170. .ds ,] ,
  171. .ds [< " \&
  172. .ds >]
  173. .\" reference formmating strings
  174. .ds c] , \&
  175. .ds n] "" and \&
  176. .ds m] "" and \&
  177. .ds a] " \&
  178. .\" reference formmating macros
  179. .de s[   \" start reference
  180. .nh
  181. .IP [\\*([F] 5m
  182. ..
  183. .de e[   \" end reference
  184. .[-
  185. ..
  186. .de []   \" start to display collected references
  187. .SH
  188. References
  189. .LP
  190. ..
  191. .de ][   \" choose format
  192. .ie !"\\*([J"" \{\
  193. .    ie !"\\*([V"" .nr t[ 1    \" journal
  194. .    el            .nr t[ 5    \" conference paper
  195. .\}
  196. .el .ie !"\\*([B"" .nr t[ 3    \" article in book
  197. .el .ie !"\\*([R"" .nr t[ 4    \" technical report
  198. .el .ie !"\\*([I"" .nr t[ 2    \" book
  199. .el                .nr t[ 0    \" other
  200. .\\n(t[[
  201. ..
  202. .de 0[   \" other
  203. .s[
  204. .if !"\\*([A"" \\*([A,
  205. .if !"\\*([T"" \\*([T,
  206. .if !"\\*([O"" \\*([O\c
  207. .if !"\\*([D"" , \\*([D\c
  208. \&.
  209. .e[
  210. ..
  211. .de 1[ \" journal article
  212. .s[
  213. .if !"\\*([A"" \\*([A,
  214. .if !"\\*([T"" \\*([T,
  215. \\fI\\*([J \\*([V\\fP,
  216. .if !"\\*([N"" \\*([N
  217. .if !"\\*([D"" (\\*([D),
  218. .if !"\\*([P"" \\*([P\c
  219. .if !"\\*([I"" , \\*([I\c
  220. \\&.
  221. .if !"\\*([O"" \\*([O.
  222. .e[
  223. ..
  224. .de 2[ \" book
  225. .s[
  226. .ie !"\\*([A"" \\*([A,
  227. .el .if !"\\*([E"" \{\
  228. .       ie \\n([E-1 \\*([E, eds.,
  229. .       el \\*([E, ed.,\}
  230. .if !"\\*([T"" \\fI\\*([T\\fP,
  231. .rm a[
  232. .if !"\\*([I"" .ds a[ \\*([I
  233. .if !"\\*([C"" \{\
  234. .       if !"\\*(a["" .as a[ , \\&
  235. .       as a[ \\*([C\}
  236. .if !"\\*([D"" \{\
  237. .       if !"\\*(a["" .as a[ , \\&
  238. .       as a[ \\*([D\}
  239. \\*(a[.
  240. .if !"\\*([G"" Gov. ordering no. \\*([G.
  241. .if !"\\*([O"" \\*([O.
  242. .e[
  243. ..
  244. .de 3[ \" article in book
  245. .s[
  246. .if !"\\*([A"" \\*([A,
  247. .if !"\\*([T"" \\*([T,
  248. in \\fI\\*([B\\fP,
  249. .if !"\\*([V"" vol. \\*([V,
  250. .if !"\\*([E"" \\*([E (ed.),
  251. .if !"\\*([I"" \\*([I,
  252. .if !"\\*([C"" \\*([C,
  253. .if !"\\*([D"" \\*([D\c
  254. .if !"\\*([P"" , \\*([P\c
  255. \\&.
  256. .if !"\\*([O"" \\*([O.
  257. .e[
  258. ..
  259. .de 4[ \" report
  260. .s[
  261. .if !"\\*([A"" \\*([A,
  262. \\*([T,
  263. \\*([R\c
  264. .if !"\\*([G"" \& (\\*([G)\c
  265. .if !"\\*([I"" , \\*([I\c
  266. .if !"\\*([C"" , \\*([C\c
  267. .if !"\\*([D"" , \\*([D\c
  268. \\&.
  269. .if !"\\*([O"" , \\*([O.
  270. .e[
  271. ..
  272. .de 5[ \" conference paper
  273. .s[
  274. .if !"\\*([A"" \\*([A,
  275. .if !"\\*([T"" \\*([T,
  276. \\fI\\*([J\\fP,
  277. .if !"\\*([C"" \\*([C\c
  278. .if !"\\*([D"" , \\*([D\c
  279. .if !"\\*([P"" , \\*([P\c
  280. \\&.
  281. .if !"\\*([O"" , \\*([O.
  282. .e[
  283. ..
  284. .de [-   \" clean up after yourself
  285. .rm [A [B [C [D
  286. .rm [E [F [G
  287. .rm [I [J [K
  288. .rm [N [O [P
  289. .rm [R [T
  290. .rm [V [W
  291. ..
  292. .if t \{ \
  293. .pl 29.7c    \" page length
  294. .po 2.5c    \" page offset (left margin)
  295. .ll 16.5c    \" line length
  296. .lt 16.5c    \" title length
  297. .nr LL 16.5c
  298. .nr )l 29.7c
  299. .nr hm 2c
  300. .nr $r 9    \" factor for vertical spacing
  301. .nr $R \n($r
  302. .sz 12        \" font size
  303. .nr pp 12
  304. .nr sp 12
  305. .nr tp 12
  306. .nr fp 10
  307. .hc ~        \" hyphenation character
  308. .        \" Umlauts and sharp s
  309. .ds A \(A:
  310. .ds O \(O:
  311. .ds U \(U:
  312. .ds a \(a:
  313. .ds o \(o:
  314. .ds u \(u:
  315. .ds s \(ss
  316. .        \"  UMLAUT  \*:u, etc.
  317. .ds : \v'-0.6m'\h'(1u-(\\n(.fu%2u))*0.13m+0.06m'\z.\h'0.2m'\z.\h'-((1u-(\\n(.fu%2u))*0.13m+0.26m)'\v'0.6m'
  318. .\}
  319. .if n \{ \
  320. .po 0        \" page offset (left margin)
  321. .ll 78        \" line length
  322. .lt 78        \" title length
  323. .nr $r 4    \" factor for vertical spacing
  324. .nr $R \n($r
  325. .hc ~        \" hyphenation character
  326. .        \" Umlaute und scharfes s
  327. .ds A Ae
  328. .ds O Oe
  329. .ds U Ue
  330. .ds a ae
  331. .ds o oe
  332. .ds u ue
  333. .ds s sz
  334. .\}
  335. .de _
  336. \&\\$1\l'|0\(ul'\\$2
  337. ..
  338. .de FT        \" font for programs
  339. .ft C
  340. .sz -2
  341. ..
  342. .de FR
  343. .ft R
  344. .sz +2
  345. ..
  346. .de []        \" start to display collected references
  347. .uh References
  348. .lp
  349. ..
  350. .de $0        \" collect table of contents
  351. .(x
  352. .ta 2c
  353. .ie '\\$2''    \\$1
  354. .el \\$2.    \\$1
  355. .)x
  356. ..
  357. .de np
  358. .nr $p +1
  359. .ip \\n($p.
  360. ..
  361. .de SH
  362. .sp 0.5
  363. .in -3
  364. .r \\$1
  365. .sp 0.5
  366. .in +3
  367. ..
  368. .de PP
  369. .sp 0.5
  370. ..
  371. .de IP
  372. .ip \\$1 \\$2
  373. ..
  374. .de I
  375. .i \\$1
  376. ..
  377. .de TH
  378. ..
  379. .EQ
  380. delim off
  381. gsize 10
  382. gfont R
  383. .EN
  384. .b " "
  385. .sp 1c
  386. .ta 9c
  387. .ft R
  388. .sz 12
  389. \l'17.1c'
  390. .nf
  391.  
  392.  
  393.     Lalr - A Generator for
  394.     Efficient Parsers
  395.  
  396.     J. Grosch
  397.  
  398.  
  399. \l'17.1c'
  400. .sp 12.5c
  401. \l'17.1c'
  402. .ft H
  403. .nf
  404.     GESELLSCHAFT F\*UR MATHEMATIK
  405.     UND DATENVERARBEITUNG MBH
  406.  
  407.     FORSCHUNGSSTELLE F\*UR
  408.     PROGRAMMSTRUKTUREN
  409.     AN DER UNIVERSIT\*AT KARLSRUHE
  410. .r
  411. \l'17.1c'
  412. .bp
  413. .oh ''LR-Parser'%'
  414. .eh ''LR-Parser'%'
  415. .ce 99
  416. .sz 20
  417. .b " "
  418. .sp 2
  419. Project
  420. .sp
  421. .b "Compiler Generation"
  422. .sp
  423. .sz 12
  424. \l'15c'
  425. .sp
  426. .sz 16
  427. .b "Lalr - A Generator for Efficient Parsers"
  428. .sp 2
  429. Josef Grosch
  430. .sp 2
  431. .sz 14
  432. Oct. 7, 1988
  433. .sp
  434. .sz 12
  435. \l'15c'
  436. .sp 2
  437. Report No. 10
  438. .sp 2
  439. Copyright \(co 1988 GMD
  440. .sp 2
  441. Gesellschaft f\*ur Mathematik und Datenverarbeitung mbH
  442. Forschungsstelle an der Universit\*at Karlsruhe
  443. Vincenz-Prie\*snitz-Str. 1
  444. D-7500 Karlsruhe
  445. .ce 0
  446. .bp
  447. .ds R \(rh
  448. .\" ds R \(RA
  449. .de FT
  450. .ft C
  451. .sz -2
  452. .vs 10
  453. ..
  454. .de $p
  455. .sp 1.5
  456. .ne 2c
  457. .ps 10
  458. .if '\\$3'' \{\
  459. .ce
  460. .tr aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ
  461. \fR\\$1\fP
  462. .tr aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzz
  463. .\}
  464. .if '\\$3'1' \{\
  465. .ce
  466. .tr aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ
  467. \fR\\$1\fP
  468. .tr aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzz
  469. .\}
  470. .if '\\$3'2' \{\
  471. \fB\\$1\fP
  472. .\}
  473. .ps
  474. .sp 0.1
  475. ..
  476. .nr pp 10
  477. .nr sp 10
  478. .nr tp 10
  479. .\" nr $r 5.3    \" factor for vertical spacing
  480. .nr $r 12    \" factor for vertical spacing
  481. .nr $R \n($r
  482. .sz 10
  483. .ce 99
  484. .sz 12
  485. .b "Lalr - A Generator for Efficient Parsers"
  486. .sz 10
  487. .sp
  488. J. Grosch
  489. .i
  490. GMD Forschungsstelle an der Universit\*at Karlsruhe
  491. Vincenz-Prie\*snitz-Str. 1, D-7500 Karlsruhe, Germany
  492. grosch@karlsruhe.gmd.de
  493. .he '''%'
  494. .bp 1
  495. .b
  496. SUMMARY
  497. .ce 0
  498. .lp
  499. .i Lalr
  500. .b
  501. is a parser generator that generates very fast and powerful parsers.
  502. The design goals have been to generate portable, table-driven parsers that
  503. are as efficient as possible and which include all the features needed for
  504. practical applications. Like \fIYacc\fP it accepts LALR(1) grammars,
  505. resolves ambiguities with precedence and associativity of operators,
  506. generates table-driven parsers, and has a mechanism for S-attribution.
  507. Unlike \fIYacc\fP it allows grammars to be written in extended BNF,
  508. includes automatic error reporting, recovery, and repair, and
  509. generates parsers in C or Modula-2.
  510. In case of LR-conflicts, a derivation tree is printed instead of the
  511. involved states and items in order to aid the location of the problem.
  512. The parsers are two to three times faster as those of \fIYacc\fP.
  513. Using a MC 68020 processor, 35,000 tokens per second or 580,000 lines per
  514. minute can be parsed. The sources of Lalr exist in C and in Modula-2.
  515. We describe in detail the development steps of the generated parsers.
  516. We show how software engineering methods like pseudo code and stepwise
  517. refinement can turn a parsing algorithm from a textbook into a complete and
  518. efficient implementation. We present the details of the
  519. generated parsers and show how the performance is achieved with a relatively
  520. simple and short program. We discuss important features of the generator
  521. and finally present a comparison of some parser generators.
  522. .sp
  523. .lp
  524. KEY WORDS  syntactic analysis  parser generator  LALR(1) grammar
  525. .sh 1 Introduction
  526. .pp
  527. The parser generator \fILalr\fP has been developed with the aim of combining
  528. a powerful specification technique for context-free languages with the
  529. generation of highly efficient parsers. As the parser generator processes
  530. the class of LALR(1) grammars, we chose the name \fILalr\fP to express
  531. the power of the specification technique.
  532. .pp
  533. The grammars may be written using extended BNF constructs. Each grammar rule
  534. may be associated with a semantic action consisting of arbitrary statements
  535. written in the target language. Whenever a grammar rule is recognized by the
  536. generated parser, the associated semantic action is executed. A mechanism for
  537. S-attribution (only synthesized attributes) is provided to allow
  538. communication between the semantic actions.
  539. .pp
  540. In case of LR-conflicts a derivation tree is printed to aid the location of
  541. the problem. The conflict can be resolved by specifying precedence and
  542. associativity for terminals and rules. Syntactic errors are handled fully
  543. automatically by the generated parsers including error reporting, recovery,
  544. and repair. The mentioned features are discussed in more detail in one of
  545. the following sections.
  546. .pp
  547. The generated parsers are table-driven. The comb-vector technique\*([<\*([[ASU86\*(]]\*(>]
  548. is used to compress the parse tables. The sources of the generator \fILalr\fP
  549. exist in the languages C and Modula-2. Parsers can be generated in the
  550. languages C and Modula-2, too. The generator uses the algorithm described by
  551. DeRemer and Pennello\*([<\*([[DeP82\*(]]\*(>]
  552. to compute the look-ahead sets.
  553. .\" although the algorithm published by .[ives.] promises to perform better.
  554. Currently \fILalr\fP runs on several workstations under UNIX.
  555. .pp
  556. Parsers generated by \fILalr\fP are two to three times as fast as
  557. \fIYacc\fP\*([<\*([[Joh75\*(]]\*(>] generated
  558. ones. They reach a speed of 35,000 tokens per second or 580,000 lines per
  559. minute on a MC 68020 processor, excluding the time for scanning.
  560. The sizes of the parsers are 25 to 40% larger than those produced by
  561. \fIYacc\fP (resulting in e. g. 37 KB for Ada).
  562. The reason is mainly due to additional code for error recovery, as well as
  563. a small space penalty for the increase of speed.
  564. .\" .pp
  565. .\" Many compiler specialists from industry believe that automatically generated
  566. .\" parsers are not efficient enough for production compilers.
  567. .\" They have been right in the past.
  568. .\" We expect to improve the situation with
  569. .\" .i Lalr,
  570. .\" a parser generator that generates very fast parsers.
  571. .\" Like \fIYacc\fP\*([<\*([[Joh75\*(]]\*(>] it accepts LALR(1) grammars,
  572. .\" resolves ambiguities with precedence and associativity of operators,
  573. .\" generates table-driven parsers, and
  574. .\" has a mechanism for S-attribution.
  575. .\" Unlike \fIYacc\fP it allows grammars to be written in extended BNF,
  576. .\" includes automatic error recovery, error reporting, and error repair, and
  577. .\" generates parsers in C or Modula-2.
  578. .\" The parsers are twice as fast as those of \fIYacc\fP.
  579. .\" Using a MC 68020 processor nearly 580,000 lines per minute can be parsed.
  580. .\" Lalr is implemented in Modula-2.
  581. .\" .pp
  582. .\" Pennello\*([<\*([[Pen86\*(]]\*(>] reports a speed-up of 10 for LR-parsers through a
  583. .\" translation of the parse tables into assembly code.
  584. .\" A disadvantage lies in the increase of the code size.
  585. .\" .pp
  586. .\" For large grammars the advantage of Pennellos implementation is lost as
  587. .\" reported in\*([<\*([[KlM89\*(]]\*(>].
  588. .\" In this case an efficient table-driven parsers is
  589. .\" superior both in time and space. Speed-up numbers have to be treated with
  590. .\" caution, too, because they heavily depend on the object chosen for
  591. .\" comparison. Every number can be reached by an "appropriate" choice.
  592. .pp
  593. Recently some researchers report that very fast LR parsers can be achieved
  594. by generating direct code, in which the parse tables are converted
  595. into executable statements.
  596. Pennello\*([<\*([[Pen86\*(]]\*(>] generates assembly code and reports that the
  597. resulting parsers run six to ten times faster than
  598. table-driven parsers generated by an unspecified generator.
  599. He measured a speed of 500,000 lines per minute on a computer similar to a
  600. VAX 11/780 and 240,000 lines per minute on an Intel 80286.
  601. A disadvantage of this
  602. solution is the increase of the parser size by a factor of two to four,
  603. mainly because a second parser is needed for error recovery.
  604. .pp
  605. Whitney and Horspool\*([<\*([[HoW89\*(],WhH88\*(]]\*(>]
  606. generate C code and report the generation of parsers between five and seven
  607. times faster than those produced by \fIYacc\fP,
  608. resulting in a speed of 95,500 to 142,000 tokens
  609. per second or 700,000 to 2 million lines per minute for parsers for C and
  610. Pascal. The parser size lies in the same range of \fIYacc\fP. Currently,
  611. error recovery, S-attribution, and semantic actions are not provided.
  612. .\" Obviously the speed-up factor and the absolute speed are contradictory to
  613. .\" our results.
  614. In the last section, we discuss the problems with this kind of
  615. measurement and conclude that the results are not comparable.
  616. .pp
  617. Currently, table-driven parsers and direct code schemes are hard to compare.
  618. First, direct code schemes do not as yet implement error recovery,
  619. S-attribution, or semantic actions.
  620. However, for realistic applications these features are necessary and of
  621. course cost some time (see below).
  622. Second, the speed of the direct code
  623. schemes decreases with the grammar size. We also made experiments with
  624. direct code parsers\*([<\*([[KlM89\*(]]\*(>] and found for example in the case
  625. of Ada that an efficient table-driven parser was superior both in speed and
  626. space.
  627. A further problem is that the code directly generated for large grammars may
  628. be too big to be translated under the restrictions of usual compilers.
  629. .pp
  630. According to A\*smann\*([<\*([[Ass88\*(]]\*(>] a typical compiler
  631. spends 25% of the time for lexical analysis, 15% for syntactic analysis, 35%
  632. for symbol table handling and semantic analysis, and 25% for code generation.
  633. In our own experiments, syntactic analysis took 5 to 10% when all
  634. compiler parts were constructed as efficiently as possible.
  635. Therefore, improving the speed of the syntactic analysis phase can reduce
  636. the total compilation time by only a few percent. However, an engineer wants
  637. all the compiler parts to be as good as possible. An engineer also wants a
  638. parser generator to have all the features needed for practical
  639. applications, such as error recovery, S-attribution, and semantic actions.
  640. .pp
  641. From this engineering point of view we decided to follow the table-driven
  642. approach. This avoids the disadvantages of the direct code parsers like
  643. assembly code, large parsers, and trouble with compiler restrictions for big
  644. programs. On the other hand, fast table-driven parsers can be generated, and
  645. can include error recovery, S-attribution, and semantic actions
  646. with as few space and time expenses as possible.
  647. .pp
  648. This paper shows that a speed-up between two and three times faster than
  649. \fIYacc\fP is possible using a table-driven implementation programmed in C.
  650. With this approach, the code size increases only by 25 to 40%, mainly because
  651. of added features like error recovery.
  652. The improvement is possible by carefully designing the encoding of the
  653. parser actions, the details of the parsing algorithm, and the structure of
  654. the parse tables.
  655. In the following we will discuss the implementation of the generated parsers
  656. as well as some important features of the generator \fILalr\fP and
  657. present a comparison to other parser generators.
  658. .sh 1 "The Generated Parser"
  659. .pp
  660. This section describes the parsers generated by \fILalr\fP.
  661. We develop the parsing
  662. algorithm step by step as given below. We will use a pseudo code notation
  663. except in the last step where we introduce C code.
  664. .(b
  665. .vs 12
  666. - basic LR-parsing algorithm
  667. - LR(0) reductions
  668. - encoding of the table entries
  669. - semantic actions and S-attribution
  670. - table representation and access
  671. - error recovery
  672. .\" - implementation issues
  673. - mapping pseudo code to C
  674. .)b
  675. .pp
  676. To be able to formally handle scanners, stacks, and grammars, we assume
  677. three modules. We only give the headings of the exported procedures
  678. consisting out of the procedure name and the types of the parameters and
  679. results.
  680. .(b
  681. .vs 12
  682. .FT
  683. MODULE scanner
  684.    PROCEDURE GetToken     (): Vocabulary
  685.    PROCEDURE GetAttribute (): <any type>
  686. .)b
  687. .lp
  688. Each call of the function GetToken yields the next token of the input. If
  689. the input is read completely, GetToken yields the special value EndOfInput.
  690. A call of the function GetAttribute returns the attributes of the current
  691. token, such as symbol tables indices for identifiers or values of numbers.
  692. .(b
  693. .vs 12
  694. .FT
  695. MODULE stack
  696.    PROCEDURE Push         (Stack, Element)
  697.    PROCEDURE Pop          (Stack): Element
  698.    PROCEDURE Top          (Stack): Element
  699. .)b
  700. .lp
  701. A stack is defined as usual.
  702. .(b
  703. .vs 12
  704. .FT
  705. MODULE grammar
  706.    PROCEDURE Length       (Productions): Integer
  707.    PROCEDURE LeftHandSide (Productions): Nonterminals
  708.    PROCEDURE Semantics    (Productions): <action statements>
  709. .)b
  710. .lp
  711. The function Length returns the length of the right-hand side of a
  712. production. The function LeftHandSide returns the nonterminal on the
  713. left-hand side of a production. The function Semantics maps every production
  714. to some action statements. These statements should be executed whenever the
  715. associated production is recognized or reduced.
  716. .sh 2 "Basic LR-Parsing Algorithm"
  717. .pp
  718. We start by looking in a textbook on compiler construction\*([<\*([[ASU86\*(],WaG84\*(]]\*(>].
  719. (Following\*([<\*([[DeP82\*(]]\*(>] we use the notion
  720. \fIread\fP action for what is usually called \fIshift\fP action.)
  721. An LR-Parser is controlled by a parse
  722. table implementing the following function
  723. .(b
  724. Table : States \(mu Vocabulary \(-> Actions
  725. .)b
  726. where
  727. .(b
  728. Actions = ( read \(mu States ) \(cu ( reduce \(mu Productions ) \(cu { halt, error }
  729. .)b
  730. .(z L
  731. .vs 12
  732. \fBAlgorithm 1:\fP Basic LR parser
  733.  
  734. .FT
  735. BEGIN
  736.    Push (StateStack, StartState)
  737.    Terminal := GetToken ()
  738. .sp 0.5
  739.    LOOP
  740.       CASE Table (Top (StateStack), Terminal) OF
  741. .sp 0.5
  742.       read t:     Push (StateStack, t)
  743.                   Terminal := GetToken ()
  744. .sp 0.5
  745.       reduce p:   FOR i := 1 TO Length (p) DO
  746.                      State := Pop (StateStack)
  747.                   END
  748.                   Nonterminal := LeftHandSide (p)
  749. .sp 0.5
  750.                   CASE Table (Top (StateStack), Nonterminal) OF
  751.                      read t: Push (StateStack, t)
  752.                   END
  753. .sp 0.5
  754.       error:      ErrorRecovery ()
  755. .sp 0.5
  756.       halt:       EXIT
  757. .sp 0.5
  758.       END
  759.    END
  760. END
  761. .)z
  762. .pp
  763. The table controls a general LR parsing algorithm (Algorithm 1).
  764. This is a pushdown
  765. automaton which remembers the parsing of the left context in a stack of
  766. states. Depending on the state on top of the stack and on the actual
  767. look-ahead symbol, it accesses the parse table and executes the obtained action.
  768. .pp
  769. There are two places where the table is accessed. Depending on the second
  770. argument of the function Table, we will call these places
  771. .i terminal
  772. and
  773. .i nonterminal
  774. accesses. At a terminal access, all four actions are possible.
  775. Nonterminals appear after
  776. reductions, only a read action is possible at a nonterminal access: no
  777. error action can occur. Nevertheless we use a CASE statement at a
  778. nonterminal access to decode the action, because there will be more cases
  779. in the next step.
  780. .sh 2 "LR(0) Reductions"
  781. .pp
  782. The textbooks also tell us about LR(0) reductions or read-reduce actions
  783. \*([[WaG84\*(]].
  784. For most languages 50% of the states are LR(0) reduce states, in which a
  785. reduce action is determined without examining the look-ahead token.
  786. The introduction of a read-reduce action
  787. is probably one of the best available optimizations.
  788. This saves many table accesses and considerable table space.
  789. .(b
  790. Actions = ( read \(mu States ) \(cu ( reduce \(mu Productions ) \(cu ( read-reduce \(mu Productions ) \(cu { halt, error }
  791. .)b
  792. .(z L
  793. .vs 12
  794. \fBAlgorithm 2:\fP LR parser with LR(0) reductions
  795.  
  796. .FT
  797. BEGIN
  798.    Push (StateStack, StartState)
  799.    Terminal := GetToken ()
  800. .sp 0.5
  801.    LOOP
  802.       CASE Table (Top (StateStack), Terminal) OF
  803. .sp 0.5
  804.       read t:        Push (StateStack, t)
  805.                      Terminal := GetToken ()
  806. .sp 0.5
  807.       read-reduce p: Push (StateStack, _)
  808.                      Terminal := GetToken ()
  809.                      GOTO L
  810. .sp 0.5
  811.       reduce p:  L:  LOOP
  812.                         FOR i := 1 TO Length (p) DO
  813.                            State := Pop (StateStack)
  814.                         END
  815.                         Nonterminal := LeftHandSide (p)
  816. .sp 0.5
  817.                         CASE Table (Top (StateStack), Nonterminal) OF
  818. .sp 0.5
  819.                            read t:        Push (StateStack, t)
  820.                                           EXIT
  821. .sp 0.5
  822.                            read-reduce p: Push (StateStack, _)
  823. .sp 0.5
  824.                         END
  825.                      END
  826. .sp 0.5
  827.       error:         ErrorRecovery ()
  828. .sp 0.5
  829.       halt:          EXIT
  830. .sp 0.5
  831.       END
  832.    END
  833. END
  834. .)z
  835. .pp
  836. As we did not find an LR parsing algorithm that uses read-reduce actions in
  837. the literature we present our version in Algorithm 2.
  838. The character '_' stands for
  839. a value that doesn't matter. A read-reduce action can occur at both places
  840. of table access. In the terminal case, we combine a read and a reduce
  841. action. In the nonterminal case we have to "virtually" read the nonterminal
  842. and then to execute a reduction. This is accomplished by the inner LOOP
  843. statement. A
  844. reduce action can be followed by a series of read-reduce actions. The inner
  845. LOOP statement is terminated on reaching a read action.
  846. .pp
  847. This solution with an inner LOOP statement has two advantages: First, as there are
  848. only two cases within the second CASE statement, it can be turned into an
  849. IF statement. Second, there is no need to differentiate between read and
  850. read-reduce with respect to terminal or nonterminal table access, as these
  851. different kinds of access occur at two different places.
  852. .sh 2 "Encoding of the Table Entries"
  853. .pp
  854. The next problem is how to efficiently represent the table entries.
  855. Conceptually, these entries are pairs consisting of an action indicator and a
  856. number denoting a state or a production. A straightforward representation
  857. using a record wastes too much space and is too hard to decode for
  858. interpretation. It is advantageous to represent the table entries by simple
  859. integers in the following way:
  860. .(b
  861. Table : States \(mu Vocabulary \(-> INTEGER
  862. .)b
  863. where
  864. .(b
  865. .vs 12
  866. .TS
  867. ;
  868. l l l.
  869. action    integer value    constant name
  870. _
  871. error           0           NoState
  872. read 1          1
  873. \&...
  874. read n          n
  875. read-reduce 1    n + 1       FirstReadReduce
  876. \&...
  877. read-reduce m    n + m
  878. reduce 1        n + m + 1    FirstReduce
  879. \&...
  880. reduce m        n + m + m
  881. halt            n + m + m + 1    Stop
  882. .TE
  883. .)b
  884. .pp
  885. The constant n stands for the number of states and the constant m
  886. for the number of productions. As it is not possible to "read-reduce" every
  887. production, not all numbers between n+1 and n+m are used.
  888. The advantage of this solution is that the table entries do not take much
  889. space, and that to decode them the CASE statements can be turned into three
  890. simple comparisons as shown in Algorithm 3.
  891. We neglect the actions error and halt for the moment, and reintroduce them in
  892. later sections.
  893. .(z L
  894. .vs 12
  895. \fBAlgorithm 3:\fP LR parser with actions encoded by integers
  896.  
  897. .FT
  898. BEGIN
  899.    Push (StateStack, StartState)
  900.    Terminal := GetToken ()
  901. .sp 0.5
  902.    LOOP
  903.       State := Table (Top (StateStack), Terminal)
  904. .sp 0.5
  905.       IF State >= FirstReadReduce THEN          /* reduce or read-reduce? */
  906. .sp 0.5
  907.          IF State < FirstReduce THEN            /* read-reduce */
  908.             Push (StateStack, _)
  909.             Terminal := GetToken ()
  910.             Production := State - FirstReadReduce + 1
  911.          ELSE                                   /* reduce */
  912.             Production := State - FirstReduce + 1
  913.          END
  914. .sp 0.5
  915.          LOOP                                   /* reduce */
  916.             FOR i := 1 TO Length (Production) DO
  917.                State := Pop (StateStack)
  918.             END
  919.             Nonterminal := LeftHandSide (Production)
  920. .sp 0.5
  921.             State := Table (Top (StateStack), Nonterminal)
  922. .sp 0.5
  923.             IF State < FirstReadReduce THEN     /* read */
  924.                Push (StateStack, State)
  925.                EXIT
  926.             ELSE                                /* read-reduce */
  927.                Push (StateStack, _)
  928.             END
  929.          END
  930. .sp 0.5
  931.       ELSE                                      /* read */
  932.          Push (StateStack, State)
  933.          Terminal := GetToken ()
  934.       END
  935.    END
  936. END
  937. .)z
  938. .\" .pp
  939. .\" In practice read-reduce actions will not occur for all productions. In this
  940. .\" sense we are wasting integer codes. But as we chose to differentiate between
  941. .\" reduce and read-reduce by a test whether odd or even we have no other way.
  942. .sh 2 "Semantic Actions and S-Attribution"
  943. .pp
  944. For the implementation of an S-attribution which is evaluated during LR parsing,
  945. the parser has to maintain a second stack for the attribute values.
  946. This stack grows and shrinks in parallel with the existing stack for the states.
  947. Algorithm 4 shows how these features have to be added.
  948. .(z L
  949. .vs 12
  950. \fBAlgorithm 4:\fP LR parser with action statements and S-attribution
  951.  
  952. .FT
  953. BEGIN
  954.    Push (AttributeStack, _)
  955.    Push (StateStack, StartState)
  956.    Terminal := GetToken ()
  957. .sp 0.5
  958.    LOOP
  959.       State := Table (Top (StateStack), Terminal)
  960. .sp 0.5
  961.       IF State >= FirstReadReduce THEN          /* reduce or read-reduce? */
  962. .sp 0.5
  963.          IF State < FirstReduce THEN            /* read-reduce */
  964.             Push (AttributeStack, GetAttribute ())
  965.             Push (StateStack, _)
  966.             Terminal := GetToken ()
  967.             Production := State - FirstReadReduce + 1
  968.          ELSE                                   /* reduce */
  969.             Production := State - FirstReduce + 1
  970.          END
  971. .sp 0.5
  972.          LOOP                                   /* reduce */
  973.             FOR i := 1 TO Length (Production) DO
  974.                Dummy := Pop (AttributeStack)
  975.                State := Pop (StateStack)
  976.             END
  977.             Nonterminal := LeftHandSide (Production)
  978. .sp 0.5
  979.             Semantics (Production) ()
  980. .sp 0.5
  981.             State := Table (Top (StateStack), Nonterminal)
  982. .sp 0.5
  983.             IF State < FirstReadReduce THEN     /* read */
  984.                Push (AttributeStack, SynAttribute)
  985.                Push (StateStack, State)
  986.                EXIT
  987.             ELSE                                /* read-reduce */
  988.                Push (AttributeStack, SynAttribute)
  989.                Push (StateStack, _)
  990.             END
  991.          END
  992. .sp 0.5
  993.       ELSE                                      /* read */
  994.          Push (AttributeStack, GetAttribute ())
  995.          Push (StateStack, State)
  996.          Terminal := GetToken ()
  997.       END
  998.    END
  999. END
  1000. .)z
  1001. .pp
  1002. In order to be able to access the attributes of all right-hand side symbols, we
  1003. need a stack with direct access, because the attribute for the i-th symbol
  1004. (counting from 1) has to be accessed by
  1005. .(b
  1006. .FT
  1007. AttributeStack [StackPointer + i]
  1008. .)b
  1009. The action statement can compute an attribute value for the left-hand side
  1010. of the production which has to be assigned to the variable SynAttribute (for
  1011. a synthesized attribute). After executing the action statements, this value
  1012. is pushed onto the attribute stack by the parser to reestablish the invariant
  1013. of the algorithm. The attribute values for terminals have to be provided by
  1014. the scanner.
  1015. .pp
  1016. As many of the terminals don't bear any attribute, most of the associated
  1017. Push operations could be replaced by pushing a dummy value: that is, an
  1018. increment of the stack pointer would be enough. To be able to distinguish
  1019. between two kinds of Push operations, two kinds of read actions would be
  1020. necessary. To make the decision would cost an extra check for every token.
  1021. We did not use this optimization because we believe that the
  1022. extra checks cost as much as the saved assignments.
  1023. .\" .sh 2 "Partial Evaluation of the Reduce Actions"
  1024. .pp
  1025. How do we implement the mapping of a production to the associated 
  1026. action statements? Of course, the natural
  1027. .\" and probably only
  1028. solution is a CASE
  1029. statement. The access to the Length and the LeftHandSide also depends on
  1030. the production. One choice would be to access two arrays. As array access is
  1031. relatively expensive, we can move these computations into the CASE statement
  1032. which we already need for the action statements. In each case, these
  1033. computations are turned into constants. The FOR loop disappears anyway,
  1034. because it suffices to decrement the stack pointers. The code common to all
  1035. reductions is not included in the CASE statement but follows afterwards.
  1036. We also factor out the code common to all parts of the IF statement at the
  1037. end of each reduction (Algorithm 5).
  1038. .(z L
  1039. .vs 12
  1040. \fBAlgorithm 5:\fP LR parser with CASE statement
  1041.  
  1042. .FT
  1043. BEGIN
  1044.    Push (AttributeStack, _)
  1045.    Push (StateStack, StartState)
  1046.    Terminal := GetToken ()
  1047. .sp 0.5
  1048.    LOOP
  1049.       State := Table (Top (StateStack), Terminal)
  1050. .sp 0.5
  1051.       IF State >= FirstReadReduce THEN          /* reduce or read-reduce? */
  1052. .sp 0.5
  1053.          IF State < FirstReduce THEN            /* read-reduce */
  1054.             Push (AttributeStack, GetAttribute ())
  1055.             Push (StateStack, _)
  1056.             Terminal := GetToken ()
  1057.          END
  1058. .sp 0.5
  1059.          LOOP                                   /* reduce */
  1060.             CASE State OF
  1061. .sp 0.5
  1062.             Stop:       HALT
  1063. .sp 0.5
  1064.             ...
  1065. .sp 0.5
  1066.             p+FirstReadReduce-1, p+FirstReduce-1:
  1067. .sp 0.5
  1068.                FOR i := 1 TO Length (p) DO
  1069.                   Dummy := Pop (AttributeStack)
  1070.                   State := Pop (StateStack)
  1071.                END
  1072.                Nonterminal := LeftHandSide (p)
  1073.                Semantics (p) ()
  1074. .sp 0.5
  1075.             q+FirstReadReduce-1, q+FirstReduce-1:
  1076. .sp 0.5
  1077.                AttributeStackPointer -:= m
  1078.                StateStackPointer     -:= m
  1079.                Nonterminal            := n
  1080. .sp 0.5
  1081.                <action statements for q>        /* Semantics (q) */
  1082. .sp 0.5
  1083.             ...
  1084. .sp 0.5
  1085.             END
  1086. .sp 0.5
  1087.             State := Table (Top (StateStack), Nonterminal)
  1088.             Push (AttributeStack, SynAttribute)
  1089.             Push (StateStack, State)
  1090. .sp 0.5
  1091.             IF State < FirstReadReduce THEN EXIT END /* read */
  1092.          END
  1093. .sp 0.5
  1094.       ELSE                                      /* read */
  1095.          Push (AttributeStack, GetAttribute ())
  1096.          Push (StateStack, State)
  1097.          Terminal := GetToken ()
  1098.       END
  1099.    END
  1100. END
  1101. .)z
  1102. .pp
  1103. Parts of the code in the case alternatives can be evaluated during generation time.
  1104. In Algorithm 5, p and q stand for arbitrary productions. Whereas in the case
  1105. of p the code has just been carried over from Algorithm 4, the case of q
  1106. contains the code after applying constant folding: the FOR loop
  1107. reduces to a decrement of the stack pointers and the precomputation of the
  1108. left-hand side of q yields a constant:
  1109. .(b
  1110. m = Length (q)
  1111. n = LeftHandSide (q)
  1112. .)b
  1113. .pp
  1114. The two stacks could use one common stack pointer if this were an array
  1115. index. As we want to arrive at real pointers in a C implementation, we have
  1116. to distinguish between the two stack pointers.
  1117. .pp
  1118. The halt action (Stop) can be treated as a special case of a reduction. It
  1119. occurs when the production S' \(-> S # is recognized. We have augmented the
  1120. given grammar by this production where
  1121. .(b
  1122. .ta 1c
  1123. S    is the original start symbol
  1124. S'    is the new start symbol
  1125. #    is the end of input token
  1126. .)b
  1127. By this we assure that the complete input is parsed and checked for
  1128. syntactical correctness.
  1129. .sh 2 "Table Representation and Access"
  1130. .pp
  1131. After developing the principle algorithm for LR-parsing, the question of
  1132. how to implement the function Table has to be discussed before we turn to
  1133. the details of the implementation. The most natural solution might be to
  1134. use a two-dimensional array. For large languages like Ada this array would
  1135. become quite big:
  1136. .(b
  1137. ( 95 terminals + 252 nonterminals ) * 540 states * 2 bytes = 374,760 bytes
  1138. .)b
  1139. This amount may be bearable with todays main memory capacities. However, we
  1140. have chosen the classical solution of compressing the sparse matrix.
  1141. Using this compression the storage required for the Ada parser is reduced to
  1142. 22,584 bytes, including additional information for error recovery. The
  1143. decision of how to compress the table has to take into account the desired
  1144. storage reduction and the cost of accessing the compressed data structure.
  1145. .pp
  1146. An advantageous compression method is the comb-vector
  1147. technique described in\*([<\*([[ASU86\*(]]\*(>] which is used for example in
  1148. \fIYacc\fP\*([<\*([[Joh75\*(]]\*(>] and in the latest version of PGS\*([<\*([[KlM89\*(]]\*(>].
  1149. This technique combines very good compression quality with fast access.
  1150. The rows (or columns) of a sparse matrix are merged into a single vector
  1151. called Next. Two additional vectors called Base and Check are necessary to
  1152. accomplish the access to the original data. Base contains for every row
  1153. (column) the offset where it starts in Next. Check contains for every entry
  1154. in Next the original row (column) index. The resulting data structure
  1155. resembles the merging of several combs into one. The optional combination
  1156. with a fourth array called Default allows further compression of the array,
  1157. as parts common to more than one row (column) can be factored out.
  1158. Algorithm 6 shows how to access the compressed data structure if rows are
  1159. merged. For more details see\*([<\*([[ASU86\*(]]\*(>].
  1160. .(b L
  1161. .vs 12
  1162. .sp 0.5
  1163. \fBAlgorithm 6:\fP access to the compressed table (comb-vector)
  1164.  
  1165. .FT
  1166. PROCEDURE Table (State, Symbol)
  1167.    LOOP
  1168.       IF Check [Base [State] + Symbol] = State THEN
  1169.          RETURN Next [Base [State] + Symbol]
  1170.       ELSE
  1171.          State := Default [State]
  1172.          IF State = NoState THEN RETURN error END
  1173.       END
  1174.    END
  1175. END
  1176. .)b
  1177. .pp
  1178. With this kind of compression it is possible to reduce the table size
  1179. to less than 10%. The space and time behaviour can be improved even more,
  1180. yielding in the case of Ada a size reduction of 6%.
  1181. Algorithm 6 may return the value "error". However, if
  1182. Symbol is a nonterminal, no errors can occur, as nonterminals are computed
  1183. during reductions and are always correct. Therefore, in the case of
  1184. nonterminal access, if Default is omitted the vector Check can be omitted,
  1185. too. In order to implement this it is necessary to split the function
  1186. Table in two parts, one for terminal and one for nonterminal access:
  1187. .(b
  1188. .TS
  1189. ;
  1190. l l l.
  1191. TTable    : States \(mu Terminals    \(-> INTEGER
  1192. NTTable    : States \(mu Nonterminals    \(-> INTEGER
  1193. .TE
  1194. .)b
  1195. .pp
  1196. The terminal Table TTable is accessed as before using Algorithm 6.
  1197. The access to the nonterminal Table NTTable can be simplified as shown in
  1198. Algorithm 7. Only the vectors NTNext and NTBase are necessary in this case.
  1199. .(b L
  1200. .vs 12
  1201. .sp 0.5
  1202. \fBAlgorithm 7:\fP access to the nonterminal table
  1203.  
  1204. .FT
  1205. PROCEDURE NTTable (State, Symbol)
  1206.    RETURN NTNext [NTBase [State] + Symbol]
  1207. END
  1208. .)b
  1209. .pp
  1210. Splitting the table into two parts has several advantages: the storage
  1211. reduction is improved because the two parts pack better if handled
  1212. independently. The storage reduction by omitting Default and Check is
  1213. greater than using these two vectors. The table access time in the
  1214. nonterminal case is improved significantly.
  1215. .pp
  1216. A further possibility to reduce space is to make the arrays Next and Check
  1217. only as large as the significant entries require. Then a check has to be
  1218. inserted to see if the expression 'Base [State] + Symbol' is within the array
  1219. bounds. We decided to save this check by increasing the arrays to a size
  1220. where no bounds violations can occur.
  1221. .sh 2 "Error Recovery"
  1222. .pp
  1223. The error recovery of \fILalr\fP
  1224. .\" and its connection to the parsing algorithm
  1225. .\" is only described in principle due to the limited space.
  1226. .\" We follow
  1227. follows the complete backtrack-free method described by
  1228. \*([[R\*oh76\*(],R\*oh80\*(],R\*oh82\*(]].
  1229. The error recovery used by \fILalr\fP is completely automatic and includes
  1230. error reporting, recovery, and repair.
  1231. From the user's point of view it works as described in a later section.
  1232. .pp
  1233. There is only one place where an error can occur: in an access to the
  1234. terminal table where
  1235. the lookahead token is not a legal continuation of the program
  1236. recognized so far. The algorithm for error recovery replaces in the
  1237. access of the terminal table (Algorithm 6) the return of the value "error".
  1238. The parsing algorithm has two modes: the \fIregular mode\fP and the
  1239. \fIrepair mode\fP used during error repair. A problem is
  1240. that during repair mode reductions and the associated semantic actions have
  1241. to be executed. To avoid duplication of this code we use the same code
  1242. during both modes. In order to avoid the immediate generation of new errors
  1243. in repair mode error messages and skipping of tokens
  1244. are disabled in this mode. Repair mode is exited when we can
  1245. accept a token at one of the two places where tokens are read.
  1246. We add an instruction at these places to leave repair mode.
  1247. .pp
  1248. It might be argued that this additional instruction to leave repair mode
  1249. could be avoided. This is true, if either the code for reductions and
  1250. semantic actions were duplicated or turned into a procedure which could be
  1251. called twice. The first solution would increase the code size significantly.
  1252. This is avoided in the second solution, but we have to pay for a
  1253. procedure call at every reduction. This is more expensive than a simple
  1254. assignment to change the mode for every input token, because the number of
  1255. input tokens is usually about the same as the number of reductions.
  1256. .if 0 \{\
  1257. .sh 2 "Implementation Issues"
  1258. .pp
  1259. After developing the principle algorithms for LR-parsing, table access, and
  1260. error recovery this chapter summarizes the implementation issues discussed
  1261. so far:
  1262. .ip -
  1263. Allowing ambiguous grammars and using precedence and associativity to solve
  1264. LR-conflicts, makes the majority of chain productions unnecessary and saves
  1265. the according
  1266. reduce actions. This kind of elimination of chain productions improves
  1267. the run time behaviour without the disadvantage of increasing the table size.
  1268. .ip -
  1269. The introduction of read-reduce actions saves for up to 50% of the
  1270. reduce actions one table access and the decoding of the table entry.
  1271. .ip -
  1272. The table entries are simple integers which consume little space and are
  1273. easy to decode and interpret.
  1274. In comparison to records with two fields as entries only one "field" has to
  1275. be accessed. In comparison to "bit stuffing" schemes using logical
  1276. instructions or
  1277. multiplication to code two numbers into one there is no need to decode by
  1278. masking or division.
  1279. .ip -
  1280. The separation of the terminal and the nonterminal table access causes 3
  1281. kinds of table entries to be enough. This allows simple decoding.
  1282. .ip -
  1283. To decode the table entries 3 simple comparisons with integer constants
  1284. suffice, there is no need for expensive CASE statements.
  1285. .ip -
  1286. No procedure call is necessary to execute semantic actions, as these are
  1287. inserted in-line.
  1288. .ip -
  1289. Using partial evaluation to access the length and the left-hand side of
  1290. productions two accesses to arrays can be turned into two constants.
  1291. .ip -
  1292. Implementing the tables with the comb-vector technique combines good storage
  1293. compression with fast access. Splitting the table into a terminal and a
  1294. nonterminal part allows further improvements.
  1295. .ip -
  1296. Treating the halt action as a special case of a reduction results in no
  1297. costs to detect this action.
  1298. .ip -
  1299. The detection of the error action is for free, as this check is already
  1300. necessary to access the terminal table.
  1301. .ip -
  1302. Using the regular parsing loop during error recovery seems to be a good
  1303. compromise. A simple assignment statement executed for
  1304. each input token avoids duplication of the semantic actions or the cost
  1305. of a procedure call.
  1306. .ip -
  1307. Of course, the procedures of algorithms 6 and 7 are inserted in-line.
  1308. .ip -
  1309. Most compilers translate IF statements so that the ELSE part is more
  1310. efficient to execute than the THEN part. That is why we have placed the read
  1311. action in an ELSE part as it seems to be a little bit more probable than a
  1312. reduce action.
  1313. .lp
  1314. .\}
  1315. .sh 2 "Mapping Pseudo Code to C"
  1316. .pp
  1317. The remaining implementation decisions are how to map the pseudo code
  1318. instructions into real programming language statements. This concerns
  1319. primarily the operations Push and Top and the table access.
  1320. The following arguments
  1321. hold only for the language C, as things are different in Modula-2.
  1322. .pp
  1323. The communication of the attribute value of a token from the scanner is not
  1324. done by the procedure GetAttribute but by the global variable Attribute.
  1325. .pp
  1326. Stacks are implemented as arrays which are administered by a stack pointer.
  1327. If the stack pointer is a register variable a Push operation could be
  1328. accomplished by one machine instruction on an appropriate machine if auto
  1329. increment is used. We preferred post increment, because we use a MC 68020
  1330. processor.
  1331. .(b
  1332. .FT
  1333. Push (AttributeStack, Attribute)   \*R   * yyAttrStackPtr ++ = Attribute;
  1334. .)b
  1335. .pp
  1336. The operation Top turns into dereferencing a pointer.
  1337. .(b
  1338. .FT
  1339. Top (StateStack)   \*R   * yyStateStackPtr
  1340. .)b
  1341. .pp
  1342. A dummy value is easily pushed by an increment instruction.
  1343. .(b
  1344. .FT
  1345. Push (StateStack, _)   \*R   yyStateStackPtr ++;
  1346. .)b
  1347. .pp
  1348. The vector NTBase does not contain integer values but direct pointers into
  1349. the vector NTNext to indicate where the rows start in NTNext.
  1350. These pointers are initialized after loading of the program. This saves the
  1351. addition of the start address of NTNext during the outer array access.
  1352. The start address is already preadded to the elements of the vector NTBase.
  1353. This kind of access is probably cheaper than the access to an uncompressed
  1354. two-dimensional array which usually involves multiplication.
  1355. The same technique is applied to the vector Base of the terminal table.
  1356. .(b
  1357. .FT
  1358. State := NTNext [NTBase [Top (StateStack ())] + Symbol]   \*R  
  1359. yyState = * (yyNTBasePtr [* yyStateStackPtr] + yyNonterminal);
  1360. .)b
  1361. .pp
  1362. The terminal table access is handled as follows.
  1363. Instead of implementing the vectors Next and Check as separate arrays,
  1364. .\" which would be equivalent to a record of arrays
  1365. we used one array of records. The array is called Comb and the records have
  1366. two fields called Check and Next. This transformation saves one array access,
  1367. because whenever we have computed the address of the Check field we find
  1368. the Next field besides it.
  1369. .(b
  1370. .vs 12
  1371. .FT
  1372. LOOP
  1373.    IF Check [Base [State] + Symbol] = State THEN
  1374.       RETURN Next [Base [State] + Symbol]
  1375.    ELSE
  1376.       State := Default [State]
  1377.       IF State = NoState THEN <error recovery> END
  1378.    END
  1379. END
  1380. .sp 0.5
  1381. \*R
  1382. .)b
  1383. .(b
  1384. .vs 12
  1385. .FT
  1386. for (;;) {
  1387.    typedef struct { int Check, Next; } yyTCombType;
  1388.    register yyTCombType * TCombPtr;
  1389. .sp 0.5
  1390.    TCombPtr = yyTBasePtr [yyState] + yyTerminal;
  1391.    if (TCombPtr->Check == yyState) {
  1392.       yyState = TCombPtr->Next;
  1393.       break;
  1394.    };
  1395.    if ((yyState = yyDefault [yyState]) != yyNoState) continue;
  1396. .sp 0.5
  1397.    < code for error recovery >
  1398. }
  1399. .)b
  1400. .pp
  1401. To check for stack overflow we have to add the code below at every read
  1402. (terminal) action. Read-reduce and reduce actions can only cause the stacks
  1403. to grow by at most one element and therefore don't need an overflow check.
  1404. We have implemented the stacks as flexible arrays. In case of stack overflow
  1405. the sizes of the arrays are increased automatically. Therefore from the
  1406. users point of view stack overflow never occurs.
  1407. .(b
  1408. .FT
  1409. if (yyStateStackPtr >= yyMaxPtr) < allocate larger arrays and copy the contents >
  1410. .)b
  1411. .pp
  1412. Of course we have used the register attribute for the most used variables:
  1413. .(b
  1414. .FT
  1415. yyState, yyTerminal, yyNonterminal, yyStateStackPtr, yyAttrStackPtr, TCombPtr
  1416. .)b
  1417. .pp
  1418. The variables yyTerminal and yyNonterminal have the type \fClong\fP
  1419. because they are involved in address computations. These have to be
  1420. performed with long arithmetic in C. The \fPlong\fP declaration saves
  1421. explicit machine instructions for length conversions (at least on MC 68020
  1422. processors). The variable yyState has the type \fPshort\fP in order to be
  1423. compatible with the type of the table elements. These have the type
  1424. \fPshort\fP to keep the table size reasonable small.
  1425. .pp
  1426. Continue statements have been changed to explicit gotos, because some
  1427. compilers don't generate optimal jump instructions.
  1428. .pp
  1429. The appendix shows an example of a parser generated by \fILalr\fP. The
  1430. error recovery, which constitutes most of the code, and some other parts
  1431. have been omitted.
  1432. Some details may deviate from the above description which concentrated
  1433. primarily on the principles. For example all identifiers carry the prefix
  1434. \&'yy' to avoid conflicts with identifiers introduced by the user into the
  1435. semantic actions.
  1436. Also, the sizes of the arrays are greater than really necessary as we used a
  1437. non-dense coding for the terminal symbols.
  1438. .sh 1 "The Parser Generator"
  1439. .pp
  1440. This chapter will discuss important features of the generator
  1441. \fILalr\fP from the user's point of view.
  1442. .sh 2 "Structure of Specification"
  1443. .pp
  1444. The structure of a parser specification is shown in Figure 1.
  1445. There may be five sections to include arbitrary target code,
  1446. which may contain declarations to be used in the semantic
  1447. actions or statements for initialization and finalization of data structures.
  1448. The TOKEN section defines the terminals of the grammar
  1449. and their encoding. In the OPER (for operator) section, precedence and
  1450. associativity for terminals can be specified to resolve LR-conflicts. The
  1451. RULE section contains the grammar rules and semantic actions.
  1452. A complete definition of the specification language can be found in the user
  1453. manual\*([<\*([[GrV88\*(]]\*(>].
  1454. .(b I
  1455. .vs 12
  1456. .sp 0.5
  1457. .FT
  1458. EXPORT { external declarations }
  1459. GLOBAL { global   declarations }
  1460. LOCAL  { local    declarations }
  1461. BEGIN  { initialization code   }
  1462. CLOSE  { finalization   code   }
  1463. TOKEN    coding of terminals
  1464. OPER     precedence of operators
  1465. RULE     grammar rules and semantic actions
  1466.  
  1467. .ft R
  1468. .sz 10
  1469. Fig. 1: Structure of Specification
  1470. .)b
  1471. .sh 2 "Semantic Actions and S-Attribution"
  1472. .pp
  1473. A parser for practical applications has more to do than just syntax checking:
  1474. it must allow some kind of translation of the recognized input. In the
  1475. case of LR parsing, action statements can be associated with the productions.
  1476. These statements are executed whenever the production is reduced.
  1477. .pp
  1478. Additionally, during LR parsing it is possible to evaluate an S-attribution
  1479. (only synthesized attributes). This mechanism works as follows:
  1480. every terminal or nonterminal of the grammar can be associated with an
  1481. attribute. After a reduction (that is during the execution of the action
  1482. statements) the attributes of the symbols on the right-hand side of the
  1483. reduced production can be accessed from an attribute stack using the notation $i.
  1484. The action statement can compute an attribute value for the left-hand side
  1485. of the production which has to be assigned to the special variable $$.
  1486. After executing the action statements, this value
  1487. is pushed onto the attribute stack by the parser to reestablish the invariant
  1488. of the algorithm. The attribute values for terminals have to be provided by the scanner.
  1489. Figure 2 shows an example for the syntax of grammar rules, semantic actions, and
  1490. S-attribution.
  1491. .(b I
  1492. .vs 12
  1493. .sp 0.5
  1494. .FT
  1495. expr : expr '+' expr { $$.value := $1.value + $3.value; } .
  1496. expr : expr '*' expr { $$.value := $1.value * $3.value; } .
  1497. expr : '(' expr ')'  { $$.value := $2.value; } .
  1498. expr : number        { $$.value := $1.value; } .
  1499.  
  1500. .ft R
  1501. .sz 10
  1502. Fig. 2: Grammar Rules with Semantic Actions and S-Attribution
  1503. .)b
  1504. .sh 2 "Ambiguous Grammars"
  1505. .pp
  1506. The grammar of Figure 2 as well as the example in Figure 3 are typical
  1507. examples of ambiguous grammars. Like \fIYacc\fP we allow resulting
  1508. LR-conflicts to be resolved
  1509. by specifying precedence and associativity for terminals in the OPER
  1510. section. Figure 4 gives an example. The lines represent increasing levels of
  1511. precedence. LEFT, RIGHT, and NONE denote left-associativity,
  1512. right-associativity, and no associativity. Rules can inherit the properties
  1513. of a terminal with the PREC suffix.
  1514. .(b I
  1515. .vs 12
  1516. .sp 0.5
  1517. .FT
  1518. stmt : IF expr THEN stmt             PREC LOW
  1519.      | IF expr THEN stmt ELSE stmt   PREC HIGH .
  1520.  
  1521. .ft R
  1522. .sz 10
  1523. Fig. 3: Ambiguous Grammar (Dangling Else)
  1524. .)b
  1525. .(b I
  1526. .vs 12
  1527. .FT
  1528. OPER  LEFT '+'
  1529.       LEFT '*'
  1530.       NONE LOW
  1531.       NONE HIGH
  1532.  
  1533. .ft R
  1534. .sz 10
  1535. Fig. 4: Resolution of LR-Conflicts Using Precedence and Associativity
  1536. .)b
  1537. .sh 2 "LR-Conflict Message"
  1538. .(z I
  1539. .vs 12
  1540. .FT
  1541. State 266
  1542. .sp 0.5
  1543. read reduce conflict
  1544. .sp 0.5
  1545. \&program End-of-Tokens 
  1546. \&PROGRAM identifier params ';' block '.' 
  1547. \&..............................:
  1548. \&:
  1549. \&labels consts types vars procs BEGIN stmts END 
  1550. \&.....................................:
  1551. \&:
  1552. \&stmt 
  1553. \&IF expr THEN stmt ELSE stmt 
  1554.                :
  1555.                IF expr THEN stmt 
  1556.                :
  1557. reduce stmt -> IF expr THEN stmt. {ELSE} ?
  1558. read   stmt -> IF expr THEN stmt.ELSE stmt ?
  1559.  
  1560. .ft R
  1561. .sz 10
  1562. Fig. 5: Derivation Tree for an LR-Conflict (Dangling Else)
  1563. .)z
  1564. .pp
  1565. To help a user locate the reason for LR-conflicts, we adopted the method
  1566. proposed by\*([<\*([[DeP82\*(]]\*(>]. Besides reporting the type of
  1567. the conflict and the involved items (whatever that is for the user) like most
  1568. LR parser generators do, the system also prints a derivation tree.
  1569. Figure 5 shows an
  1570. example. It shows how the items and the look-ahead tokens get into the
  1571. conflict situation. In general there can be two trees if the derivations for
  1572. the conflicting items are different. Each tree consists of three parts. An
  1573. initial part begins at the start symbol of the grammar. At a certain node
  1574. (rule) two subtrees explain the emergence of the item and the look-ahead.
  1575. .pp
  1576. Every line contains a right-hand side of a grammar rule. Usually the
  1577. right-hand side is indented to start below the nonterminal of the left-hand
  1578. side. To avoid line overflow, dotted edges also refer to the left-hand side
  1579. nonterminal and allow a shift back to the left margin. In Figure 5 the
  1580. initial tree part consists of 5 lines (not counting the dotted lines). The
  1581. symbols \fIstmt\fP and ELSE are the roots of the other two tree parts. This
  1582. location is indicated by the "unnecessary" colon in the following line.
  1583. After one intermediate line the left subtree derives the conflicting items.
  1584. The right subtree consists in this case only of the root node (the terminal
  1585. \&ELSE) indicating the look-ahead. In general this can be a tree of
  1586. arbitrary size. The LR-conflict can easily be seen from this tree fragment.
  1587. If conditional statements are nested as shown, then there is a read reduce
  1588. conflict (also called shift reduce conflict).
  1589. .sh 2 "Error Recovery"
  1590. .(z I
  1591. .vs 12
  1592. Source Program:
  1593. .sp 0.5
  1594. .FT
  1595. program test (output);
  1596. begin
  1597.    if (a = b] write (a);
  1598. end.
  1599. .sp 0.5
  1600. .sz 10
  1601. .r
  1602. Error Messages:
  1603. .sp 0.5
  1604. .FT
  1605. 3, 13: Error       syntax error     
  1606. 3, 13: Information expected symbols: ')' '*' '+' '-' '/' '<' '<=' '=' '<>'
  1607.                                      '>' '>=' AND DIV IN MOD OR
  1608. 3, 15: Information restart point    
  1609. 3, 15: Repair      symbol inserted : ')'
  1610. 3, 15: Repair      symbol inserted : THEN
  1611.  
  1612. .ft R
  1613. .sz 10
  1614. Fig. 6: Example of Automatic Error Messages
  1615. .)z
  1616. .pp
  1617. The generated parsers include information and algorithms to handle syntax
  1618. errors completely automatically.
  1619. We follow the complete backtrack-free method described by
  1620. \*([[R\*oh76\*(],R\*oh80\*(],R\*oh82\*(]]
  1621. and provide expressive reporting, recovery, and repair. Every incorrect input
  1622. is "virtually" transformed into a syntactically correct program with the
  1623. consequence of only executing a "correct" sequence of semantic actions.
  1624. Therefore the following compiler phases like semantic analysis don't have to
  1625. bother with syntax errors. \fILalr\fP provides a prototype error module which
  1626. prints messages as shown in Figure 6.
  1627. Internally the error recovery works as follows:
  1628. .ip - 0.5c
  1629. The location of the syntax error is reported.
  1630. .ip - 0.5c
  1631. All the tokens that would be a legal continuation of the program are
  1632. computed and reported.
  1633. .ip - 0.5c
  1634. All the tokens that can serve to continue parsing are computed. A minimal
  1635. sequence of tokens is skipped until one of these tokens is found.
  1636. .ip - 0.5c
  1637. The recovery location is reported.
  1638. .ip - 0.5c
  1639. Parsing continues in the so-called repair mode. In this mode the parser
  1640. behaves as usual except that no tokens are read from the input. Instead a
  1641. minimal sequence of tokens is synthesized to repair the error.
  1642. The parser stays in this mode until the input token can be accepted.
  1643. The synthesized tokens are reported. The program can be regarded as
  1644. repaired, if the skipped tokens are replaced by the synthesized ones.
  1645. Upon leaving repair mode, parsing continues as usual.
  1646. .sh 1 "Comparison of Parser Generators"
  1647. .pp
  1648. Finally we present a comparison of \fILalr\fP with some other parser
  1649. generators that we have access to. We are comparing the features of the
  1650. generators and the performance of the generated parsers. Tables 1 to 4 contain
  1651. the results and should be self explanatory.
  1652. Besides \fILalr\fP we examine:
  1653. .ta 1.5c
  1654. .ip - 0.5c
  1655. Yacc    well known from UNIX\*([<\*([[Joh75\*(]]\*(>]
  1656. .ip - 0.5c
  1657. Bison    public domain remake of \fIYacc\fP\*([<\*([[GNU88\*(]]\*(>]
  1658. .ip - 0.5c
  1659. PGS    Parser Generating System also developed at Karlsruhe\*([<\*([[GrK86\*(],KlM89\*(]]\*(>]
  1660. .ip - 0.5c
  1661. Ell    recursive descent parser generator described in\*([<\*([[Gro88\*(]]\*(>].
  1662. .EQ
  1663. delim $$
  1664. .EN
  1665. .(b L
  1666. .ce
  1667. .sp 0.5
  1668. Table 1: Comparison of Specification Techniques for Parser Generators
  1669. .sp 0.5
  1670. .TS
  1671. tab (;) box center;
  1672. l | l l l l l
  1673. l | l l l l l.
  1674.                  ;Bison  ;Yacc   ;PGS    ;Lalr   ;Ell
  1675. _
  1676. specification language;BNF    ;BNF    ;EBNF   ;EBNF   ;EBNF
  1677. grammar class    ;LALR(1);LALR(1);LALR(1);LALR(1);LL(1)
  1678.                  ;       ;       ;LR(1)  ;       ;
  1679.                  ;       ;       ;SLR(1) ;       ;
  1680. semantic actions ;yes    ;yes    ;yes    ;yes    ;yes
  1681. S-attribution    ;numeric;numeric;symbolic;numeric;-
  1682. L-attribution    ;-      ;-      ;-      ;-      ;symbolic
  1683. .TE
  1684. .)b
  1685. .pp
  1686. .i Lalr ,
  1687. PGS, and
  1688. .i Ell
  1689. accept grammars written in extended BNF whereas
  1690. .i Yacc
  1691. and
  1692. .i Bison
  1693. require grammars in BNF. The tools
  1694. .i Lalr ,
  1695. PGS,
  1696. .i Yacc ,
  1697. and
  1698. .i Bison
  1699. process the large class of LALR(1) grammars but can only evaluate an S-attribution during
  1700. parsing.
  1701. .i Ell
  1702. on the other hand processes the smaller class of LL(1) grammars but generates parsers which
  1703. are 50% faster (see below) and can evaluate a more powerful L-attribution during parsing.
  1704. .(b L
  1705. .ce
  1706. .sp 0.5
  1707. Table 2: Features for Grammar Conflicts and Error Recovery
  1708. .sp 0.5
  1709. .TS
  1710. tab (;) box center;
  1711. l | l l l l l
  1712. l | l l l l l.
  1713.                  ;Bison  ;Yacc   ;PGS    ;Lalr   ;Ell
  1714. _
  1715. conflict message ;state, ;state, ;state, ;derivation-;involved
  1716.                  ;  items;  items;  items;  tree ;  productions
  1717. conflict solution;precedence;precedence;precedence;precedence;first rule
  1718.                  ;associativity;associativity;associativity;associativity;
  1719.                  ;       ;       ;modification;  ;
  1720. chain rule elimination;-      ;-      ;yes    ;-      ;-
  1721. error recovery   ;by hand;by hand;automatic;automatic;automatic
  1722. error repair     ;-      ;-      ;yes    ;yes    ;yes
  1723. .TE
  1724. .)b
  1725. .pp
  1726. In case of grammar conflicts,
  1727. .i Lalr
  1728. has the advantage of providing derivation trees to support the location and solution of this
  1729. kind of problems. The tools
  1730. .i Lalr ,
  1731. PGS, and
  1732. .i Ell
  1733. provide automatic error recovery and repair in case of syntax errors.
  1734. .(b L
  1735. .ce
  1736. .sp 0.5
  1737. Table 3: Comparison of Implementation Techniques and Languages
  1738. .sp 0.5
  1739. .TS
  1740. tab (;) box center;
  1741. l | l l l l l
  1742. l | l l l l l.
  1743.                  ;Bison  ;Yacc   ;PGS    ;Lalr   ;Ell
  1744. _
  1745. parsing method   ;table-driven;table-driven;table-driven;table-driven;recursive
  1746.                  ;       ;       ;       ;       ;  descent
  1747. table compression;comb-vector;comb-vector;comb-vector;comb-vector;-
  1748. _
  1749. implementation languages;C      ;C      ;Pascal ;C      ;C     
  1750.                         ;       ;       ;       ;Modula ;Modula
  1751. target languages ;C      ;C      ;C      ;C      ;C
  1752.                  ;       ;       ;Modula ;Modula ;Modula
  1753.                  ;       ;       ;Pascal
  1754.                  ;       ;       ;Ada
  1755. .TE
  1756. .)b
  1757. .pp
  1758. All the LALR(1) tools generate table-driven parsers and use the comb-vector technique for
  1759. table compression.
  1760. .i Ell
  1761. produces directly coded recursive descent parsers. Whereas
  1762. .i Yacc
  1763. and
  1764. .i Bison
  1765. are implemented in C and generate C code, the sources of
  1766. .i Lalr
  1767. and
  1768. .i Ell
  1769. exist in Modula-2 and in C and the tools generate Modula-2 as well as C.
  1770. PGS is implemented in Pascal and generates parsers in even more languages.
  1771. .pp
  1772. The parser measurements (Table 4) exclude time and size for scanning and refer
  1773. to experiments with Modula-2 parsers.
  1774. The grammar for the LALR(1) tools had 69 terminals, 52 nonterminals,
  1775. and 163 productions. The grammar for \fIEll\fP was in extended BNF and
  1776. contained 69 terminals, 45 nonterminals, and 91 productions. The timings
  1777. result from analyzing a big Modula-2 program containing 28,302 tokens,
  1778. 7867 lines, or 193,862 characters with the generated parsers.
  1779. For this input the parser generated from \fILalr\fP executed
  1780. 13,827 read, 14,476 read-terminal-reduce, 11,422 read-nonterminal-reduce,
  1781. and 18,056 reduce actions. The terminal Table TTable was accessed 46,358
  1782. times and the nonterminal Table NTTable 43,953 times.
  1783. .(b L
  1784. .ce
  1785. .sp 0.5
  1786. Table 4: Comparison of Parser Speeds and Sizes
  1787. .sp 0.5
  1788. .TS
  1789. tab (;) box center;
  1790. l | r r r r r
  1791. l | r r r r r.
  1792.  ;Bison;Yacc;PGS;Lalr;Ell
  1793. _
  1794. speed [$10 sup 3$ tokens/sec.];8.93;15.94;17.32;34.94;54.64
  1795. speed [$10 sup 3$ lines/min.];150;270;290;580;910
  1796. _
  1797. table size [bytes];7,724;9,968;9,832;9,620;-
  1798. parser size [bytes];10,900;12,200;14,140;16,492;18,048
  1799. _
  1800. generation time [sec.];4.92;17.28;51.04;27.46;10.48
  1801. .TE
  1802. .)b
  1803. .EQ
  1804. delim off
  1805. .EN
  1806. .pp
  1807. In the presented experiment \fILalr\fP generated parsers are twice as fast
  1808. as those of \fIYacc\fP. In general, we observed speed-ups between two and
  1809. three depending on the grammar. The sizes of the parse tables are nearly the
  1810. same in all cases.
  1811. The parser generated by \fILalr\fP is 35% larger then the \fIYacc\fP
  1812. parser, mainly because of the code for error recovery. The generation times
  1813. vary widely. The reasons can be found in the different algorithms for
  1814. computing the look-ahead sets and the quality of the implementation.
  1815. \fILalr\fP spends a considerable amount of time in printing the derivation
  1816. trees for LR-conflicts.
  1817. PGS generated parsers turned out to be faster in comparison to
  1818. .i Yacc ,
  1819. but
  1820. .i Bison
  1821. performed considerably slower. Parsers generated by
  1822. .i Ell
  1823. were found to be the fastest exceeding the speed of
  1824. .i Lalr
  1825. by 50%.
  1826. .pp
  1827. The measurements of the parser speed turned out to be a hairy business.
  1828. The results can be influenced in many ways from:
  1829. .ip - 0.5c
  1830. The hardware: we used a PCS Cadmus 9900 with a MC68020 processor running
  1831. at a clock rate of 16.7 MHz.
  1832. .ip - 0.5c
  1833. The loader: our timings include the time to load the parser which is almost
  1834. zero.
  1835. .ip - 0.5c
  1836. The compiler: we used the C compiler of PCS.
  1837. .ip - 0.5c
  1838. The language: we used Modula-2.
  1839. .ip - 0.5c
  1840. The size of the language: in the case of \fILalr\fP the size of the
  1841. language or the size of the grammar does not influence the speed of the
  1842. parser because the same table-driven algorithm and the same data structure
  1843. is used in every case. This can be different for other parsers. For example
  1844. the speed of directly coded parsers decreases with the grammar size.
  1845. One reason is that linear or binary-tree search is done to determine
  1846. the next action. Another reason can be that long jump instructions become
  1847. necessary instead of short ones.
  1848. PGS stores states in one byte if there are less than 256 states and in
  1849. two bytes otherwise. This decreases the speed for large grammars, too,
  1850. at least on byte-addressable machines.
  1851. .ip - 0.5c
  1852. The grammar style, the number of rules, especially chain rules and the
  1853. like: we used the same grammar except for \fIEll\fP which had as few chain
  1854. rules as possible and which caused as few reduce actions as possible. This
  1855. means e. g. we specified expressions in an ambiguous style like shown in
  1856. Figure 2.
  1857. .\" Exceptions are \fIEll\fP which needs an LL(1) grammar and PGS, because
  1858. .\" modifications are inelegant to resolve many ambiguities.
  1859. .ip - 0.5c
  1860. The test input: we used the same large Modula program as test data in
  1861. every case, of course.
  1862. Nevertheless the programming style or the code "density" influence the
  1863. resulting speed when it is measured in lines per minute.
  1864. .ip - 0.5c
  1865. The timing: we measured CPU-time and subtracted the scanner time from the
  1866. total time (scanner and parser) to get the parser time. We used the UNIX
  1867. shell command \fItime\fP to get the time and added user and system time.
  1868. .ip - 0.5c
  1869. The measure: we selected tokens per second as well as lines per minute as
  1870. measures. The first one is independent of the density of the input and
  1871. therefore more exact. The second one has been used by other authors and it
  1872. is more expressive for a user.
  1873. .ip - 0.5c
  1874. The semantic actions: we specified empty semantic actions for all rules in
  1875. order to simulate the conditions in a realistic application. This has more
  1876. consequences than one might think. It disables a short cut of \fIYacc\fP and
  1877. the chain rule elimination\*([<\*([[WaG84\*(]]\*(>] of PGS, decreasing the speed in
  1878. both cases.
  1879. .\" A further experiment with PGS revealed even more problems. To allow chain
  1880. .\" rule elimination we deleted the empty semantic actions for chain rules.
  1881. .\" Surprisingly, instead of getting faster the parser was slower. The reason is
  1882. .\" that chain rule elimination increases the number of states. Accidentally we
  1883. .\" exceeded the number of 256. Now states have to be stored in two bytes instead
  1884. .\" of one. The additional memory accesses are more expensive than the win from
  1885. .\" the chain rule elimination.
  1886. .pp
  1887. Our conclusion from the numerous problems with the measurement of
  1888. parser speed is that results from different environments or from different
  1889. people can not be compared. There are too many conditions that influence the
  1890. results and usually only a few of these conditions are reported.
  1891. .sh 1 "Conclusion"
  1892. .pp
  1893. We showed that table-driven, portable LR(1) parsers can be implemented
  1894. efficiently in C or similar languages. Following the presented ideas the
  1895. parser generator \fILalr\fP generates parsers that are two to three times
  1896. faster than parsers generated by \fIYacc\fP. They are vary fast and reach a
  1897. speed of 35,000 tokens per second or 580,000 lines per minute.
  1898. The generated parsers have all the features needed for practical
  1899. applications such as semantic actions, S-attribution, and error recovery.
  1900. .pp
  1901. We have shown how to develop an efficient parsing algorithm in a systematic
  1902. way. The starting point was a basic algorithm from a textbook. In a
  1903. stepwise manner we turned it into a relatively short yet efficient algorithm
  1904. mainly using pseudo code. Target code was introduced only in the last step.
  1905. .pp
  1906. We presented the main features of the parser generator \fILalr\fP
  1907. from the user's point of view. A valuable feature of \fILalr\fP is that it
  1908. prints a derivation tree in case of LR-conflicts to aid the location of
  1909. the problem.
  1910. We finally compared the features and performance of some parser generators.
  1911. .\" The description of the implementation shows how the performance is achieved.
  1912. .\" .pp
  1913. .\" We hope to have convinced the reader that this way of program development
  1914. .\" works and produces fast and compact code. Unfortunately the story told is not
  1915. .\" true. We did arrive at the presented solution and it does have the described
  1916. .\" properties. The stepwise development shown in chapter 2 would have been the
  1917. .\" right way. But in reality our path of development was a completely different
  1918. .\" and winding one. We tried to transfer the implementation of a table-driven
  1919. .\" scanner to a parser. A first paper about an early version of the parsing
  1920. .\" algorithm regarded the underlying principle completely different and
  1921. .\" contained some errors. After fixing the errors we finally discovered that
  1922. .\" the interpretation given in this paper is the right one and an ideal
  1923. .\" development should have been following the steps given in chapter 2.
  1924. .uh Acknowledgements
  1925. .pp
  1926. Whereas the author contributed the parser skeletons in C and Modula-2, the
  1927. generator program \fILalr\fP was written and debugged by Bertram Vielsack
  1928. who also provided the experimental results.
  1929. Valuable suggestions to improve this paper are due to Kai Koskimies and
  1930. Nigel Horspool.
  1931. Nick Graham deserves many thanks for transforming my text into idiomatic
  1932. English.
  1933. .fi
  1934. .sz 12
  1935. .[]
  1936. .[-
  1937. .ds [F ASU86
  1938. .ds [A A\*(p]\*(a]V\*(p] Aho
  1939. .as [A \*(c]R\*(p] Sethi
  1940. .as [A \*(m]J\*(p]\*(a]D\*(p] Ullman
  1941. .ds [T Compilers: Principles, Techniques, and Tools
  1942. .ds [I Addison Wesley
  1943. .ds [C Reading, M\&A
  1944. .ds [D 1986
  1945. .][
  1946. .[-
  1947. .ds [F Ass88
  1948. .ds [A W\*(p] Assmann
  1949. .ds [A W. A\\*smann
  1950. .ds [T A Short Review of High Speed Compilation
  1951. .ds [V 371
  1952. .ds [J LNCS
  1953. .ds [C Berlin
  1954. .ds [I Springer Verlag
  1955. .nr [P 1
  1956. .ds [P 1-10
  1957. .ds [D Oct. 1988
  1958. .][
  1959. .[-
  1960. .ds [F DeP82
  1961. .ds [A F\*(p] DeRemer
  1962. .as [A \*(n]T\*(p] Pennello
  1963. .ds [T Efficient Computation of LALR(1) Look-Ahead Sets
  1964. .nr [P 1
  1965. .ds [P 615-649
  1966. .ds [J ACM Trans. Prog. Lang. and Systems
  1967. .ds [V 4
  1968. .ds [N 4
  1969. .ds [D Oct. 1982
  1970. .][
  1971. .[-
  1972. .ds [F GNU88
  1973. .ds [A GNU\ Project
  1974. .ds [T Bison - Manual Page
  1975. .ds [I Public Domain Software
  1976. .ds [D 1988
  1977. .][
  1978. .[-
  1979. .ds [F GrK86
  1980. .ds [A J\*(p] Grosch
  1981. .as [A \*(n]E\*(p] Klein
  1982. .ds [T User Manual for the PGS-System
  1983. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1984. .ds [D Aug. 1986
  1985. .][
  1986. .[-
  1987. .ds [F Gro88
  1988. .ds [A J\*(p] Grosch
  1989. .ds [T Generators for High-Speed Front-Ends
  1990. .ds [V 371
  1991. .ds [J LNCS
  1992. .ds [C Berlin
  1993. .ds [I Springer Verlag
  1994. .nr [P 1
  1995. .ds [P 81-92
  1996. .ds [D Oct. 1988
  1997. .][
  1998. .[-
  1999. .ds [F GrV88
  2000. .ds [A J\*(p] Grosch
  2001. .as [A \*(n]B\*(p] Vielsack
  2002. .ds [T The Parser Generators Lalr and Ell
  2003. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  2004. .ds [R Compiler Generation Report No. 8
  2005. .ds [N 8
  2006. .ds [D Apr. 1988
  2007. .][
  2008. .[-
  2009. .ds [F HoW89
  2010. .ds [A R\*(p]\*(a]N\*(p] Horspool
  2011. .as [A \*(n]M\*(p] Whitney
  2012. .ds [T Even Faster LR Parsing
  2013. .ds [I University of Victoria, Department of Computer Science
  2014. .ds [R Report Dept. of Computer Science-114-IR
  2015. .ds [D May 1989
  2016. .][
  2017. .[-
  2018. .ds [F Joh75
  2019. .ds [A S\*(p]\*(a]C\*(p] Johnson
  2020. .ds [T Yacc \(em  Yet Another Compiler-Compiler
  2021. .ds [R Computer Science Technical Report 32
  2022. .ds [I Bell Telephone Laboratories
  2023. .ds [C Murray Hill, NJ
  2024. .ds [D July 1975
  2025. .][
  2026. .[-
  2027. .ds [F KlM89
  2028. .ds [A E\*(p] Klein
  2029. .as [A \*(n]M\*(p] Martin
  2030. .ds [T The Parser Generating System PGS
  2031. .ds [J Software\(emPractice & Experience
  2032. .ds [V 19
  2033. .ds [N 11
  2034. .nr [P 1
  2035. .ds [P 1015-1028
  2036. .ds [D Nov. 1989
  2037. .][
  2038. .[-
  2039. .ds [F Pen86
  2040. .ds [A T\*(p]\*(a]J\*(p] Pennello
  2041. .ds [T Very Fast LR Parsing
  2042. .ds [J SI\&GPLAN Notices
  2043. .ds [V 21
  2044. .ds [N 7
  2045. .nr [P 1
  2046. .ds [P 145-151
  2047. .ds [D July 1986
  2048. .][
  2049. .[-
  2050. .ds [F R\*oh76
  2051. .ds [A J\*(p] R\\*:ohrich
  2052. .ds [T Syntax-Error Recovery in LR-Parsers
  2053. .ds [E H\*(p] Schneider
  2054. .ds [E H.-J\*(p] Schneider
  2055. .as [E \*(n]M\*(p] Nagl
  2056. .nr [E 2
  2057. .ds [S Programmiersprachen, 4. Fachtagung der GI, Erlangen
  2058. .ds [B Informatik-Fachberichte
  2059. .ds [V 1
  2060. .nr [P 1
  2061. .ds [P 175-184
  2062. .ds [C Berlin
  2063. .ds [I Springer Verlag
  2064. .ds [D 1976
  2065. .][
  2066. .[-
  2067. .ds [F R\*oh80
  2068. .ds [A J\*(p] R\\*:ohrich
  2069. .ds [T Methods for the Automatic Construction of Error Correcting Parsers
  2070. .ds [J Acta Inf.
  2071. .ds [V 13
  2072. .ds [N 2
  2073. .nr [P 1
  2074. .ds [P 115-139
  2075. .ds [D 1980
  2076. .][
  2077. .[-
  2078. .ds [F R\*oh82
  2079. .ds [A J\*(p] R\\*:ohrich
  2080. .ds [T Behandlung syntaktischer Fehler
  2081. .ds [J Informatik Spektrum
  2082. .ds [V 5
  2083. .ds [N 3
  2084. .nr [P 1
  2085. .ds [P 171-184
  2086. .ds [D 1982
  2087. .][
  2088. .[-
  2089. .ds [F WaG84
  2090. .ds [A W\*(p]\*(a]M\*(p] Waite
  2091. .as [A \*(n]G\*(p] Goos
  2092. .ds [T Compiler Construction
  2093. .ds [I Springer Verlag
  2094. .ds [C New York, NY
  2095. .ds [D 1984
  2096. .][
  2097. .[-
  2098. .ds [F WhH88
  2099. .ds [A M\*(p] Whitney
  2100. .as [A \*(n]R\*(p]\*(a]N\*(p] Horspool
  2101. .ds [T Extremely Rapid LR Parsing
  2102. .ds [E D\*(p] Hammer
  2103. .nr [E 1
  2104. .ds [B Proceedings of the Workshop on Compiler Compiler and High Speed Compilation
  2105. .ds [C Berlin, GDR
  2106. .nr [P 1
  2107. .ds [P 248-257
  2108. .ds [D Oct. 1988
  2109. .][
  2110. .bp
  2111. .lp
  2112. .uh "Appendix"
  2113. .vs 12
  2114. .sp
  2115. .ce
  2116. Example of a Generated Parser
  2117. .sp
  2118. .nf
  2119. Grammar:
  2120. .sp
  2121. .FT
  2122. .\" TOKEN
  2123. .\"    'i'     = 105
  2124. .\"    'n'     = 110
  2125. .\"    '='     = 61
  2126. .\"    '+'     = 43
  2127. .\"    '-'     = 45
  2128. .\"    '*'     = 42
  2129. .\"    '/'     = 47
  2130. .\"    '('     = 40
  2131. .\"    ')'     = 41
  2132. .\" 
  2133. .\" OPER
  2134. .\"    LEFT    '+'     '-'
  2135. .\"    LEFT    '*'     '/'
  2136. .\" 
  2137. .\" RULE
  2138.    L       : L S | .
  2139.    S       : 'i' '=' E .
  2140.    E       : E '+' E
  2141.            | E '-' E
  2142.            | E '*' E
  2143.            | E '/' E
  2144.            | 'i'
  2145.            | 'n'
  2146.            | '(' E ')' .
  2147. .sp
  2148. .sz 10
  2149. .r
  2150. Parser:
  2151. .sp
  2152. .FT
  2153. .\" typedef int tScanAttribute;
  2154. .\" typedef int bool;
  2155. .\" # define false 0
  2156. .\" tScanAttribute Attribute;
  2157. .\" 
  2158. # include "DynArray.h"
  2159. .sp 0.5
  2160. # define yyInitStackSize        100
  2161. # define yyNoState                0
  2162. # define yyTableMax             122
  2163. # define yyNTableMax            119
  2164. # define yyLastReadState         13
  2165. # define yyFirstReadReduce       14
  2166. # define yyFirstReduce           20
  2167. # define yyStartState             1
  2168. # define yyStopState             20
  2169. .sp 0.5
  2170. typedef short   yyStateRange;
  2171. typedef struct  { yyStateRange Check, Next; } yyTCombType;
  2172. typedef struct  { tScanAttribute Scan; } tParsAttribute;
  2173. .sp 0.5
  2174. static  yyTCombType *   yyTBasePtr      [yyLastReadState + 1];
  2175. static  yyStateRange *  yyNBasePtr      [yyLastReadState + 1];
  2176. static  yyStateRange    yyDefault       [yyLastReadState + 1];
  2177. static  yyTCombType     yyTComb         [yyTableMax + 1];
  2178. static  yyStateRange    yyNComb         [yyNTableMax + 1];
  2179. static  int             yyErrorCount;
  2180. .sp 0.5
  2181. int Parse ()
  2182. {
  2183.    register yyStateRange     yyState         ;
  2184.    register long             yyTerminal      ;
  2185.    register yyStateRange *   yyStateStackPtr ;
  2186.    register tParsAttribute * yyAttrStackPtr  ;
  2187.    register bool             yyIsRepairing   ;
  2188.             unsigned long    yyStateStackSize = yyInitStackSize;
  2189.             unsigned long    yyAttrStackSize  = yyInitStackSize;
  2190.             yyStateRange *   yyStateStack    ;
  2191.             tParsAttribute * yyAttributeStack;
  2192.             tParsAttribute   yySynAttribute  ;       /* synthesized attribute */
  2193.             yyStateRange *   yyMaxPtr;
  2194. .sp 0.5
  2195.    yyState           = yyStartState;
  2196.    yyTerminal        = GetToken ();
  2197.    MakeArray (& yyStateStack, & yyStateStackSize, sizeof (yyStateRange));
  2198.    MakeArray (& yyAttributeStack, & yyAttrStackSize, sizeof (tParsAttribute));
  2199.    yyMaxPtr          = & yyStateStack [yyStateStackSize];
  2200.    yyStateStackPtr   = yyStateStack;
  2201.    yyAttrStackPtr    = & yyAttributeStack [1];
  2202.    yyErrorCount      = 0;
  2203.    yyIsRepairing     = false;
  2204. .sp 0.5
  2205. ParseLoop:
  2206.    for (;;) {
  2207.       if (yyStateStackPtr >= yyMaxPtr) {             /* stack overflow? */
  2208.          int StateStackPtr   = yyStateStackPtr - yyStateStack;
  2209.          int AttrStackPtr    = yyAttrStackPtr - yyAttributeStack;
  2210.          ExtendArray (& yyStateStack, & yyStateStackSize, sizeof (yyStateRange));
  2211.          ExtendArray (& yyAttributeStack, & yyAttrStackSize, sizeof (tParsAttribute));
  2212.          yyStateStackPtr     = yyStateStack + StateStackPtr;
  2213.          yyAttrStackPtr      = yyAttributeStack + AttrStackPtr;
  2214.          yyMaxPtr            = & yyStateStack [yyStateStackSize];
  2215.       };
  2216.       * yyStateStackPtr = yyState;
  2217. .sp 0.5
  2218. TermTrans:
  2219.       for (;;) {   /* SPEC State = Table (State, Terminal); terminal transition */
  2220.          register    yyStateRange * TCombPtr;
  2221. .sp 0.5
  2222.          TCombPtr = (yyStateRange *) (yyTBasePtr [yyState] + yyTerminal);
  2223.          if (* TCombPtr ++ == yyState) { yyState = * TCombPtr; break; };
  2224.          if ((yyState = yyDefault [yyState]) != yyNoState) goto TermTrans;
  2225. .sp 0.5
  2226.          /* error recovery */
  2227.       };
  2228. .sp 0.5
  2229.       if (yyState >= yyFirstReadReduce) {            /* reduce or read-reduce? */
  2230.          if (yyState < yyFirstReduce) {              /* read-reduce */
  2231.             yyStateStackPtr ++;
  2232.             (yyAttrStackPtr ++)->Scan = Attribute;
  2233.             yyTerminal = GetToken ();
  2234.             yyIsRepairing = false;
  2235.          };
  2236. .sp 0.5
  2237.          for (;;) {
  2238.             register long yyNonterminal;
  2239. .sp 0.5
  2240.             switch (yyState) {
  2241.    case yyStopState: /* S' : L End-of-Tokens . */
  2242.       ReleaseArray (& yyStateStack, & yyStateStackSize, sizeof (yyStateRange));
  2243.       ReleaseArray (& yyAttributeStack, & yyAttrStackSize, sizeof (tParsAttribute));
  2244.       return yyErrorCount;
  2245.    case 21:
  2246.    case 19: /* L : L S . */
  2247.       yyStateStackPtr -= 2; yyAttrStackPtr -= 2; yyNonterminal = 111; break;
  2248.    case 22: /* L : . */
  2249.       yyStateStackPtr -= 0; yyAttrStackPtr -= 0; yyNonterminal = 111; break;
  2250.    case 23: /* S : 'i' '=' E . */
  2251.       yyStateStackPtr -= 3; yyAttrStackPtr -= 3; yyNonterminal = 112; break;
  2252.    case 24: /* E : E '+' E . */
  2253.       yyStateStackPtr -= 3; yyAttrStackPtr -= 3; yyNonterminal = 113; break;
  2254.    case 25: /* E : E '-' E . */
  2255.       yyStateStackPtr -= 3; yyAttrStackPtr -= 3; yyNonterminal = 113; break;
  2256.    case 26:
  2257.    case 17: /* E : E '*' E . */
  2258.       yyStateStackPtr -= 3; yyAttrStackPtr -= 3; yyNonterminal = 113; break;
  2259.    case 27:
  2260.    case 18: /* E : E '/' E . */
  2261.       yyStateStackPtr -= 3; yyAttrStackPtr -= 3; yyNonterminal = 113; break;
  2262.    case 28:
  2263.    case 14: /* E : 'i' . */
  2264.       yyStateStackPtr -= 1; yyAttrStackPtr -= 1; yyNonterminal = 113; break;
  2265.    case 29:
  2266.    case 15: /* E : 'n' . */
  2267.       yyStateStackPtr -= 1; yyAttrStackPtr -= 1; yyNonterminal = 113; break;
  2268.    case 30:
  2269.    case 16: /* E : '(' E ')' . */
  2270.       yyStateStackPtr -= 3; yyAttrStackPtr -= 3; yyNonterminal = 113; break;
  2271.             };
  2272. .sp 0.5
  2273.             /* SPEC State = Table (Top (), Nonterminal); nonterminal transition */
  2274.             yyState = * (yyNBasePtr [* yyStateStackPtr ++] + yyNonterminal);
  2275.             * yyAttrStackPtr ++ = yySynAttribute;
  2276.             if (yyState < yyFirstReadReduce) goto ParseLoop;
  2277.          };                                          /* read-reduce? */
  2278. .sp 0.5
  2279.       } else {                                       /* read */
  2280.          yyStateStackPtr ++;
  2281.          (yyAttrStackPtr ++)->Scan = Attribute;
  2282.          yyTerminal = GetToken ();
  2283.          yyIsRepairing = false;
  2284.       };
  2285.    };
  2286. };
  2287. .bp 1
  2288. .lp
  2289. .b Contents
  2290. .sp
  2291. .xp
  2292.